package com.samxcode.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its
 * complexity.
 * 
 * Solutions:
 * 
 * the priority queue(heap)
 * 1.add each first element in the lists to the priority queue
 * 2.poll the first element in the queue, add its next node into the queue
 * @author Sam
 *
 */
public class MergeKSortedLists {

    public static void main(String[] args) {

    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq =
                new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {

                    @Override
                    public int compare(ListNode o1, ListNode o2) {
                        if (o1.val > o2.val) {
                            return 1;
                        } else if (o1.val == o2.val) {
                            return 0;
                        } else {
                            return -1;
                        }
                    }
                });
        ListNode first = new ListNode(0);
        ListNode node = first;
        for (ListNode listNode : lists) {
            if (listNode != null) {
                pq.add(listNode);
            }
        }
        while (!pq.isEmpty()) {
            node.next = pq.poll();
            node = node.next;
            if (node.next != null) {
                pq.add(node.next);
            }
        }
        return first.next;
    }
}
